/*
题目: 腐烂的橘子
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

    值 0 代表空单元格；
    值 1 代表新鲜橘子；
    值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

https://leetcode.cn/problems/rotting-oranges
 */
public class OrangesRotting {
    boolean[][] visited = null;
    int[][] dir = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public class Pair {
        public int x;
        public int y;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public int orangesRotting(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        visited = new boolean[row][col];

        Queue<Pair> queue = new LinkedList<> ();
        // 优化 : 统计一下新鲜橘子的数量, 最后判断一下新鲜的橘子还有没有
        int flesh = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 2) {
                    visited[i][j] = true;
                    queue.offer(new Pair(i, j));
                } else if (grid[i][j] == 1) {
                    flesh ++;
                }
            }
        }

        int time = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();

            boolean isBad = false;
            while (size-- != 0) {
                Pair cur = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int nextX = cur.x + dir[i][0];
                    int nextY = cur.y + dir[i][1];

                    if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col)
                        continue ;

                    if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {
                        isBad = true;
                        flesh --;
                        visited[nextX][nextY] = true;
                        grid[nextX][nextY] = 2;
                        queue.offer(new Pair(nextX, nextY));
                    }
                }
            }
            // 必须要有坏水果, 才能更新传播时间
            if (isBad)  time ++;
        }

        return flesh == 0 ? time : -1;
    }
}
